//
// Description: 200. 岛屿数量
// Created by Loading on 2022/5/1.
//

#include <bits/stdc++.h>

using namespace std;

int numIslands(vector<vector<char>> &grid) {
    int m = grid.size();
    int n = grid[0].size();
    function<void(int, int)> dfs = [&](int i, int j) {
        // 标记访问过
        grid[i][j] = '#';
        // 四个方向搜寻
        if (i - 1 >= 0 && grid[i - 1][j] == '1') {
            dfs(i - 1, j);
        }
        if (i + 1 < m && grid[i + 1][j] == '1') {
            dfs(i + 1, j);
        }
        if (j - 1 >= 0 && grid[i][j - 1] == '1') {
            dfs(i, j - 1);
        }
        if (j + 1 < n && grid[i][j + 1] == '1') {
            dfs(i, j + 1);
        }
    };

    int res = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == '1') {
                ++res;
                dfs(i, j);
            }
        }
    }

    return res;
}

int main() {
    vector<vector<char>> grid{
            {'1', '1', '1', '1', '0'},
            {'1', '1', '0', '1', '0'},
            {'1', '1', '0', '0', '0'},
            {'0', '0', '0', '0', '0'}
    };
    int res = numIslands(grid);
    cout << res << endl;

    return 0;
}